/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ueb15;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

/**
 *
 * @author adier
 */
public class RedBlackTreeImpl extends TreeImpl{
	
    private NodeImpl     root = (NodeImpl) createRoot();
    //private StringBuffer operationlog   = null;

    
    @Override
    public NodeImpl getNode(Object iData) throws IllegalArgumentException {
        return super.getNode(iData);

    /*if(value==getRoot().getValue())
    {
        return root;
    }
    else
    {
                if(getNode(root, value).getValue()!=value)
                {
                        return null;
                }
                else
                {
                        return getNode(root, value);
                }
    }*/
    }


    @Override
    public NodeImpl getRoot() {
        return this.root;
    }

    /**
    * inserts iData at the right place
    * 
    * @param iData     that should be inserted
    * @return          operationlog
    * @throws IllegalArgumentException  if iData is null
    */
    public NodeImpl insertValue(Object iData) throws IllegalArgumentException {
        if (iData == null) {
                throw new IllegalArgumentException("Null einfuegen waere Schwachsinn!");
        }
        /*if(value.equals(getNode(value)))//umsonst, da es nicht ordentlich vergleicht
        {
                return getNode(value);
        }*/
        return insertVal(root,iData);
    }

    private NodeImpl insertVal(NodeImpl current, Object iData) {
        operationlog = null;
        if(current.isNil())
        {
            current.setiData(iData);
            operationlog.append(iData + "hinzugefuegt");
            current.setLeftChild((NodeImpl) createNode(current));
            current.setRightChild((NodeImpl) createNode(current));

            repairInsertion(current);

            return current;
        }

        if(((Comparable) iData).compareTo(current.getiData()) > 0)
        {
            return insertVal(current.getRightChild(), iData);
        }
        else if(((Comparable) iData).compareTo(current.getiData()) < 0)
        {
            return insertVal(current.getLeftChild(), iData);
        }
        else
        {
            return current;
        }

        /*
        if(current.isNil())
        {

            createNode(current.getParent());
            current.setValue(value);
            if(value>current.getParent().getValue())
            {
                    current.getParent().setRightChild(current);

            }
            else
            {
                    current.getParent().setLeftChild(current);
            }
        }
        if(value>current.getValue())
        {
                current=current.getRightChild();
                insertVal(current, value);
        }
        else if(value<current.getValue())
        {
                current=current.getLeftChild();
                insertVal(current,value);
        }
        return current;*/
    }

    @Override
    public int size() {
        return super.size();
    }

    /**
        * Factory method to create new nodes.
        * 
        * @param node
        *            The parent node to create.
        * @return The newly created node.
        */
    protected NodeImpl createNode(NodeImpl node) {
            return super.createNode(node);
    }

    /**
    * Factory method, that creates the root node.
    * 
    * @return The newly created root node, which is the only node without a
    *         parent.
    */
    protected NodeImpl createRoot() {
        return super.createRoot();
    }


    /**
    * Repair the tree after the node has been inserted
    * 
    * @param node The current node
    */
    @Override
    protected void repairInsertion(NodeImpl node) {
        // case 1
        if (node.isRoot()) //Fall 1
        {
            repairInsertionCase1(node);
            return;
        }
        if(node.getParent().isBlack()==true)//Fall 2
        {
            repairInsertionCase2(node);
            return;
        }
        if((node.getParent().isBlack()==false)&&(node.getUncle().isBlack()==false))//Fall 3
        {
            repairInsertionCase3(node);
            return;
        }
        if((node.getUncle().isBlack()==true)&&(node.getParent().isLeftChild()))//Fall 4
        {
            repairInsertionCase4(node);
            return;
        }
        if((node.getUncle().isBlack()==true)&&(node.getParent()==node.getGrandparent().getRightChild()))//Fall 5
        {
            repairInsertionCase5(node);
        }
    }

    /**
        * Repair insertion case 1 if node is <b>root</b>
        * 
        * @param node   The current node.
        */
    protected void repairInsertionCase1(NodeImpl node) {
        assert node.isRoot();
        node.makeBlack();
        operationlog.append("make " + node.getiData() + " black \n");
        System.out.print("make " + node.getiData() + " black \n");
    }

    /**
        * Repair insertion case 2 if parent is <b>black</b>
        * 
        * @param node   The current node.
        */
    protected void repairInsertionCase2(NodeImpl node) {
            node.makeRed();
            operationlog.append("make " + node.getiData() + " red \n");
            System.out.print("make " + node.getiData() + " red \n");
    }

    /**
    * Repair insertion case 3 if parent is <b>red</b> and uncle is <b>red</b>
    * 
    * @param node  The current node.
    */
    protected void repairInsertionCase3(NodeImpl node) {
        node.makeRed();
        operationlog.append("make " + node.getiData() + " red \n");
        System.out.print("make " + node.getiData() + " red \n");
        node.getGrandparent().makeRed();
        operationlog.append("make " + node.getGrandparent().getiData() + " red \n");
        System.out.print("make " + node.getGrandparent().getiData() + " red \n");
        node.getParent().makeBlack();
        operationlog.append("make " + node.getParent().getiData() + " black \n");
        System.out.print("make " + node.getParent().getiData() + " black \n");
        node.getUncle().makeBlack();
        operationlog.append("make " + node.getUncle().getiData() + " black \n");
        System.out.print("make " + node.getUncle().getiData() + " black \n");
        repairInsertion(node.getGrandparent());
    }

    /**
    * Repair insertion case 4 if uncle is <b>black</b> and parent is <b>leftchild</b>
    * 
    * @param node   The current node.
    */
    protected void repairInsertionCase4(NodeImpl node) {
        if(node.isRightChild())
        {
            assert node.isRightChild();
            repairInsertionCase4a(node);
        }
        else
        {
            assert node.isLeftChild();
            repairInsertionCase4b(node);
        }
    }

    /**
    * Repair insertion case 4a if node is <b>rightchild</b>
    * 
    * @param node   The current node.
    */
    protected void repairInsertionCase4a(NodeImpl node) {
        node.makeRed();
        operationlog.append("make " + node.getiData() + " red \n");
        System.out.print("make " + node.getiData() + " red \n");
        rotateLeft(node.getParent());
        repairInsertionCase4b(node.getLeftChild());

    }

    /**
    * Repair insertion case 4b if node is <b>leftchild</b>
    * 
    * @param node   The current node.
    */
    protected void repairInsertionCase4b(NodeImpl node) {
        assert node.isLeftChild();
        node.getParent().makeBlack();
        operationlog.append("make " + node.getParent().getiData() + " black \n");
        System.out.print("make " + node.getParent().getiData() + " black \n");
        node.getGrandparent().makeRed();
        operationlog.append("make " + node.getGrandparent().getiData() + " red \n");
        System.out.print("make " + node.getGrandparent().getiData() + " red \n");
        node.makeRed();
        operationlog.append("make " + node.getiData() + " red \n");
        System.out.print("make " + node.getiData() + " red \n");
        rotateRight(node.getGrandparent());
    }

    /**
    * Repair insertion case 5 if uncle is <b>black</b> and parent is <b>rightchild</b>
    * 
    * @param node   The current node.
    */
    protected void repairInsertionCase5(NodeImpl node) {
        if(node.isLeftChild())
        {
            assert node.isLeftChild();
            repairInsertionCase5a(node);
        }
        else
        {
            assert node.isRightChild();
            repairInsertionCase5b(node);
        }
    }

    /**
    * Repair insertion case 5a if node is <b>leftchild</b>
    * 
    * @param node   The current node.
    */
    protected void repairInsertionCase5a(NodeImpl node) {
            rotateRight(node.getParent());
            node.makeRed();
            operationlog.append("make " + node.getiData() + " red \n");
            System.out.print("make " + node.getiData() + " red \n");
            repairInsertionCase5b(node.getRightChild());
    }

    /**
    * Repair insertion case 5 if node is <b>rightchild</b>
    * 
    * @param node   The current node.
    */
    protected void repairInsertionCase5b(NodeImpl node) {
            node.getParent().makeBlack();
            operationlog.append("make " + node.getParent().getiData() + " black \n");
            System.out.print("make " + node.getParent().getiData() + " black \n");
            node.getGrandparent().makeRed();
            operationlog.append("make " + node.getGrandparent().getiData() + " red \n");
            System.out.print("make " + node.getGrandparent().getiData() + " red \n");
            node.makeRed();
            operationlog.append("make " + node.getiData() + " red \n");
            System.out.print("make " + node.getiData() + " red \n");
            rotateLeft(node.getGrandparent());
    }

    /**
        * Rotates the subtree of the given node left around that node.
        * 
        * @param node   The node to <i>rotate</i> around.
        */
    protected void rotateLeft(NodeImpl node) {
        System.out.print("rotate left around" + node.getiData());
        super.rotateLeft(node);
    }

    /**
        * Rotates the subtree of the given node right around that node.
        * 
        * @param node   The node to <i>rotate</i> around.
        */
    protected void rotateRight(NodeImpl node) {
        System.out.print("rotate right around" + node.getiData());
        super.rotateRight(node);
    }


    /**
     * returns the node under the current tree with iData
     * 
     * @param current   current tree
     * @param iData     iData of the node
     * @return          the searched Node
     */
    @Override
    protected NodeImpl getNode(NodeImpl current, Object iData) {
        return super.getNode(current, iData);
    }

}
    
